#pragma once
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include "RoadGraph.h"
#include "set"
#include "Constants.h"
using namespace std;

struct Point1 {
	int val;
	float remain, start; 
	Point1(int val, float start, float remain) :val(val), start(start), remain(remain) {}
};

struct Table {
	map<int, PLF> near_arrive;
	map<int, float> far_arrive;
};

struct BNode {
	vector<BNode*> child; 
	unordered_map<int, Table> arrive;
	RoadGraph* road_graph;
	float delta;

	BNode() {}

	BNode(RoadGraph* road, float delta) {
		this->road_graph = road;
		this->delta = delta;
	}

	void generateArrive() {
		int node_num = road_graph->node_num;
		cout << "node_num + cnt = " << node_num + road_graph->cnt << endl;
		for (int i = 0; i < node_num + road_graph->cnt; i++) { 

			Table temp;
			map<int, PLF> newNearArrive;
			set<int> stNear;
			stNear.emplace(i);
			getNearArrive(i, i, delta, newNearArrive, stNear);
			temp.near_arrive = newNearArrive;

			map<int, float> newFarArrive;
			set<int> stFar;
			stFar.emplace(i);
			unordered_map<int, int> countFar;
			countFar[i] = INT_MAX;
			getFarArrive(i, i, 0, delta, 0, newFarArrive, stFar, countFar);
			temp.far_arrive = newFarArrive;

			arrive[i] = { newNearArrive , newFarArrive };
		}
	}

	void getNearArrive(int parent, int nodeId, float query_time, map<int, PLF>& newNearArrive, set<int>& st) {
		unordered_map<int, float> outEdge = road_graph->nodes[nodeId]->roadOutEdge;
		for (auto out : outEdge) {
			if (st.find(out.first) != st.end()) continue;
			float cost = road_graph->nodes[nodeId]->min_max[out.first].maxValue;
			float remain = query_time - cost;
			if (remain < 0) continue;
			PLF PLFc; 
			if (parent == nodeId) { 
				PLFc.f = road_graph->nodes[nodeId]->plf[out.first].f;
			}
			else { 
				PLF front, behind;
				front.f = newNearArrive[nodeId].f;
				behind.f = road_graph->nodes[nodeId]->plf[out.first].f;
				behind.compound(front, PLFc, nodeId);
			}
			if (newNearArrive.find(out.first) != newNearArrive.end()) { 
				newNearArrive[out.first].minimize(PLFc);
			}
			else {
				newNearArrive[out.first].f = PLFc.f;
			}
			if (remain >= 0) { 
				st.emplace(out.first);
				getNearArrive(parent, out.first, remain, newNearArrive, st);
				st.erase(out.first);
			}
		}
	}

	void getFarArrive(int parent, int nodeId, float start_time, float query_time, float cost_v, map<int, float>& newFarArrive, set<int>& st, unordered_map<int, int>& count) {

		if (query_time < 0) return;
		if (query_time == 0) {
			newFarArrive[nodeId] = cost_v;
			return;
		}
		newFarArrive[nodeId] = cost_v;
		unordered_map<int, float> outEdge = road_graph->nodes[nodeId]->roadOutEdge;
		for (auto out : outEdge) {
			if (st.find(out.first) != st.end()) continue;
			float cost = road_graph->nodes[nodeId]->min_max[out.first].minValue;
			if (count.find(nodeId) != count.end() && start_time > count[nodeId]) continue;
			count[nodeId] = start_time;
			st.emplace(out.first);
			getFarArrive(parent, out.first, start_time + cost, query_time - cost, cost + cost_v, newFarArrive, st, count);
			st.erase(out.first);
		}
	}


	unordered_set<int> bidirectionSearch(int nodeId, float start_t, float delta, float sita, ofstream& fout, float& time_bmax, float& total_time) {
		clock_t tbegin1 = clock(), tend1;
		int m = ceil(sita / delta);
		int node_num = road_graph->node_num;

		vector<int> bound;
		vector<int> bound_min;
		unordered_set<int> flag;
		unordered_set<int> Bmin = getBmin(nodeId, start_t, sita, m, bound_min);

		clock_t tbegin = clock(), tend;
		unordered_set<int> Bmax = getBmax(nodeId, m, delta, bound, flag);
		tend = clock();
		time_bmax += (tend - tbegin);

		unordered_set<int> between = getBetweenBmaxBmin(Bmax, Bmin);
		unordered_set<int> temp = between;

		unordered_set<int> result;
		for (auto num : Bmin) {
			if (num >= node_num) continue;
			result.emplace(num);
		}

		vector<unordered_set<int>> Q = getQRegion(nodeId, m);
		bound_min.push_back(nodeId);
		for (int i = 1; i < m; i++) {
			if (temp.empty()) break; 
			unordered_set<int> q_region = Q[i];
			unordered_set<int> to_delete;
			for (int j = 0; j < bound.size(); j++) {
				unordered_set<int> v_max = getVmax(bound[j], m - i + 1, Bmax);
				unordered_set<int> v_min = getVmin(bound[j], m - i + 1, Bmax);
				temp.erase(bound[j]);
				if (isIntersection(v_min, q_region)) { 
					if (bound[j] < node_num) result.emplace(bound[j]);
					to_delete.emplace(bound[j]);
					bound.erase(bound.begin() + j);
					j--;
					continue;
				}
				else if (!isIntersection(v_max, q_region)) { 
					to_delete.emplace(bound[j]);
					bound.erase(bound.begin() + j);
					j--;
				}
			}
			addNeighbor(between, to_delete, flag, bound);
			if (bound.size() == 0) break;
		}

		if (!between.empty()) {
			checkOneToOne(between, Bmin, bound_min, result, Bmax, sita , start_t);
		}

		tend1 = clock();
		total_time += (tend1 - tbegin1);

		for (auto num : Bmax) {
			if (num >= road_graph->node_num) continue;
			fout << num << endl;
		}
		fout << "-1" << endl;
		return result;
	}

	unordered_set<int> bidirectionSearch(int nodeId, float start_t, float delta, float sita, float& total_time) {
		clock_t tbegin1 = clock(), tend1;
		int m = ceil(sita / delta);
		int node_num = road_graph->node_num;

		vector<int> bound;
		vector<int> bound_min;
		unordered_set<int> flag;
		unordered_set<int> Bmin = getBmin(nodeId, start_t, sita, m, bound_min);
		unordered_set<int> Bmax = getBmax(nodeId, m, delta, bound, flag);
		unordered_set<int> between = getBetweenBmaxBmin(Bmax, Bmin);
		unordered_set<int> temp = between;

		unordered_set<int> result;
		for (auto num : Bmin) {
			if (num >= node_num) continue;
			result.emplace(num);
		}

		vector<unordered_set<int>> Q = getQRegion(nodeId, m);
		bound_min.push_back(nodeId);
		for (int i = 1; i < m; i++) {
			if (temp.empty()) break; 
			unordered_set<int> q_region = Q[i];
			unordered_set<int> to_delete;
			for (int j = 0; j < bound.size(); j++) {
				unordered_set<int> v_max = getVmax(bound[j], m - i + 1, Bmax);
				unordered_set<int> v_min = getVmin(bound[j], m - i + 1, Bmax);
				temp.erase(bound[j]);
				if (isIntersection(v_min, q_region)) { 
					if (bound[j] < node_num) result.emplace(bound[j]);
					to_delete.emplace(bound[j]);
					bound.erase(bound.begin() + j);
					j--;
					continue;
				}
				else if (!isIntersection(v_max, q_region)) { 
					to_delete.emplace(bound[j]);
					bound.erase(bound.begin() + j);
					j--;
				}
			}
			addNeighbor(between, to_delete, flag, bound);
			if (bound.size() == 0) break; 
		}

		if (!between.empty()) {
			checkOneToOne(between, Bmin, bound_min, result, Bmax, sita, start_t);
		}

		tend1 = clock();
		total_time += (tend1 - tbegin1);
		return result;
	}

	void checkOneToOne(unordered_set<int>& between, unordered_set<int> Bmin, vector<int> bound_min, unordered_set<int>& result, unordered_set<int> Bmax, float sita , float start_t) {
		for (auto num : bound_min) {
			if (between.empty()) break;
			queue<Point1> que;
			que.push({ num , start_t , sita });
			set<int> st;
			st.emplace(num);
			while (!que.empty()) {
				Point1 cur = que.front();
				que.pop();
				unordered_map<int, float> outEdge = road_graph->nodes[cur.val]->roadOutEdge;
				for (auto itmap : outEdge) {
					if (st.find(itmap.first) != st.end()) continue;
					if (Bmax.find(itmap.first) != Bmax.end()) {
						float cost = road_graph->nodes[cur.val]->plf[itmap.first].dpt2wgt(cur.start);
						float remain = cur.remain - cost;
						if (remain < 0) continue;
						st.emplace(itmap.first);
						between.erase(itmap.first);
						if (itmap.first < road_graph->node_num) result.emplace(itmap.first);
						if (remain > 0) que.push({ itmap.first , cur.start + cost , remain });
					}
				}
			}
		}
	}

	bool isIntersection(unordered_set<int> region1, unordered_set<int> region2) {
		for (auto it : region1) {
			if (region2.find(it) != region2.end()) {
				return true;
				break;
			}
		}
		return false;
	}

	bool isIntersection2(unordered_set<int> region1, unordered_set<int> region2) {
		for (auto it : region1) {
			if (region2.find(it) != region2.end()) {
				return true;
				break;
			}
		}
		return false;
	}

	void addNeighbor(unordered_set<int>& between, unordered_set<int> to_delete, unordered_set<int>& flag, vector<int>& bound) {
		for (auto itSet : to_delete) {
			between.erase(itSet);
			for (auto neighbor : arrive[itSet].far_arrive) {
				if (between.find(neighbor.first) != between.end()) {
					if (flag.count(neighbor.first) == 0) {
						bound.push_back(neighbor.first);
						flag.emplace(neighbor.first);
					}
				}
			}
		}
	}

	vector<unordered_set<int>> getQRegion(int nodeId, int m) {
		unordered_set<int> st;
		queue<int> que;
		vector<unordered_set<int>> result;
		for (auto it : arrive[nodeId].near_arrive) {
			que.push(it.first);
			st.emplace(it.first);
		}
		result.push_back(st);
		for (int i = 1; i < m; i++) {
			int len = que.size();
			for (int j = 0; j < len; j++) {
				int cur = que.front();
				que.pop();
				for (auto it : arrive[cur].near_arrive) {
					if (st.count(it.first) == 0) {
						que.push(it.first);
						st.emplace(it.first);
					}
				}
			}
			unordered_set<int> temp = st;
			result.push_back(temp);
		}
		return result;
	}

	unordered_set<int> getBmin(int nodeId, float start_t, float query_time, int m, vector<int> bound) {
		queue<Point1> que;
		unordered_set<int> st;
		unordered_set<int> Bmin;
		for (auto it : arrive[nodeId].near_arrive) {
			float cost = it.second.dpt2wgt(start_t);
			float remain = query_time - cost;
			if (remain < 0) continue;
			if (remain == 0) {
				Bmin.emplace(it.first);
				continue;
			}
			Bmin.emplace(it.first);
			que.push({ it.first , start_t + cost , remain });
			st.emplace(it.first);
		}
		for (int i = 1; i < m; i++) {
			int len = que.size();
			for (int j = 0; j < len; j++) {
				Point1 cur = que.front();
				que.pop();
				for (auto it : arrive[cur.val].near_arrive) {
					if (st.find(it.first) != st.end()) continue;
					st.emplace(it.first);
					float cost = it.second.dpt2wgt(cur.start);
					float remain = cur.remain - cost;
					if (remain < 0) continue;
					if (remain == 0) {
						Bmin.emplace(it.first);
						continue;
					}
					Bmin.emplace(it.first);
					que.push({ it.first , cur.start + cost , cur.remain - cost });
					if (i == m - 1) {
						bound.push_back(it.first);
					}
				}
			}
		}
		return Bmin;
	}

	unordered_set<int> getBmax(int nodeId, int m, int delta, vector<int>& bound, unordered_set<int>& flag) {
		queue<pair<int, float>> que;
		unordered_set<int> Bmax; 
		unordered_map<int, float> Bmax_node_time;
		float min_time = DBL_MAX;
		for (auto it : arrive[nodeId].far_arrive) {
			que.push(make_pair(it.first, it.second));
			Bmax.emplace(it.first);
			if (it.first != nodeId)
				Bmax_node_time[it.first] = it.second;
		}
		for (int i = 1; i < m; i++) {
			int len = que.size();
			for (int j = 0; j < len; j++) {
				int cur = que.front().first;
				float time = que.front().second;
				que.pop();
				for (auto it : arrive[cur].far_arrive) {
					if (Bmax.count(it.first) == 0) {
						que.push(make_pair(it.first, it.second + time));
						Bmax.emplace(it.first);
						if (i == m - 1 && (m * delta - it.second + time) > 0)
							Bmax_node_time[it.first] = m * delta - it.second + time;
						if (i == m) {
							bound.push_back(it.first);
							flag.emplace(it.first);
						}
					}
				}
			}
			if (i == m - 1) {
				for (auto it : Bmax_node_time) {
					min_time = min(min_time, it.second);
				}
			}
		}
		for (int i = 0; i < ceil((m * delta - min_time) / delta); i++) {
			int len = que.size();
			for (int j = 0; j < len; j++) {
				int cur = que.front().first;
				float time = que.front().second;
				que.pop();
				for (auto it : arrive[cur].far_arrive) {
					if (Bmax.count(it.first) == 0) {
						que.push(make_pair(it.first, it.second + time));
						Bmax.emplace(it.first);
					}
				}
			}
		}
		return Bmax;
	}

	unordered_set<int> getBetweenBmaxBmin(unordered_set<int> Bmax, unordered_set<int> Bmin) {
		for (auto num : Bmin) {
			Bmax.erase(num);
		}
		return Bmax;
	}


	unordered_set<int> getVmax(int nodeId, int m, unordered_set<int> Bmax) {
		queue<int> que;
		unordered_set<int> Vmax;
		for (auto it : arrive[nodeId].far_arrive) {
			if (Bmax.find(it.first) != Bmax.end()) {
				que.push(it.first);
				Vmax.emplace(it.first);
			}
		}
		for (int i = 1; i < m; i++) {
			int len = que.size();
			for (int j = 0; j < len; j++) {
				int cur = que.front();
				que.pop();
				for (auto it : arrive[cur].far_arrive) {
					if (Vmax.count(it.first) == 0 && Bmax.find(it.first) != Bmax.end()) {
						que.push(it.first);
						Vmax.emplace(it.first);
					}
				}
			}
		}
		return Vmax;
	}
	unordered_set<int> getVmin(int nodeId, int m, unordered_set<int> Bmax) {
		queue<int> que;
		unordered_set<int> Vmin;
		for (auto it : arrive[nodeId].near_arrive) {
			if (Bmax.find(it.first) != Bmax.end()) {
				que.push(it.first);
				Vmin.emplace(it.first);
			}
		}
		for (int i = 1; i < m; i++) {
			int len = que.size();
			for (int j = 0; j < len; j++) {
				int cur = que.front();
				que.pop();
				for (auto it : arrive[cur].near_arrive) {
					if (Vmin.count(it.first) == 0 && Bmax.find(it.first) != Bmax.end()) {
						que.push(it.first);
						Vmin.emplace(it.first);
					}
				}
			}
		}
		return Vmin;
	}
};